/*
 * CopyRight (c) 2019 gcj
 * File: dynamic_program.hpp
 * Project: algorithm
 * Author: gcj
 * Date: 2019/9/19
 * Description: dynamic programming algorithm simple implementation examples
 * License: see the LICENSE.txt file
 * github: https://github.com/saber/algorithm
 */
#include "dynamic_program.hpp"
#include <iostream>
#include <vector>
using namespace std;

//! \brief 简单测试动态规划算法（0-1 背包问题（最大重量、最大价值）
//! \run
//!     g++ backtracking.test.cc -std=c++11 && ./a.out

//! \note 下面测试时，都会输出所有背包情况！
int main(int argc, char const *argv[]) {
    cout << "测试 0-1 背包最大重量问题" << endl;
    vector<int> backpack{2, 2, 4, 6, 3};
    int max_capacity = 9;
    cout << "直接利用状态矩阵方法" << endl;
    cout << glib::BackpackMaxWeight(backpack, max_capacity) << endl;  // 9
    cout << "直接利用状态向量方法" << endl;
    cout << glib::BackpackMaxWeight2(backpack, max_capacity) << endl; // 9

    cout << "测试 0-1 背包最大价值问题" << endl;
    vector<pair<int ,int>> backpack1{ // 30 组数据运行时间就在 10 s 左右了
        {71, 26}, {34, 59}, {82, 30}, {23, 19}, {1,  66}, {88, 85}, {12, 94},
        {57, 8 }, {10, 3 }, {68, 44}, {5,  5 }, {33, 1 }, {37, 41}, {69, 82},
        {98, 76}, {24, 1 }, {26, 12}, {83, 81}, {16, 73}, {26, 32}, {18, 74},
        {43, 54}, {52, 62}, {71, 41}, {22, 19}, {65, 10}, {68, 65}, {8,  53},
        {40, 56}, {40, 53}, {24, 70}, {72, 66}, {16, 58}, {34, 22}, {10, 72},
        {19, 33}, {28, 96}, {13, 88}, {34, 68}, {98, 45}, {29, 44}, {31, 61},
        {79, 78}, {33, 78}, {60, 6 }, {74, 66}, {44, 11}, {56, 59}, {54, 83},
        {17, 48}}; // 这 50 组数据最大价值量为 1063，但是自己测试没有运行出来

    vector<pair<int, int>> backpack2{
        {77, 92}, {22, 22}, {29, 87}, {50, 46}, {99, 90}
    };

    vector<pair<int, int>> backpack3{
        {95, 89}, {75, 59}, {23, 19}, {73, 43}, {50, 100},
        {22, 72}, {6 , 44}, {57, 16}, {89, 7 }, {98, 64}
    };

    vector<pair<int, int>> backpack4{
        {79, 83}, {58, 14}, {86, 54}, {11, 79}, {28, 72},
        {62, 52}, {15 , 48}, {68, 62}
    };

    int max_capacity1 = 300;
    int max_capacity2 = 100;
    int max_capacity3 = 300;
    int max_capacity4 = 200;

    cout << glib::BackpackMaxValue(backpack1, max_capacity1) << endl;  // 1063
    cout << glib::BackpackMaxValue(backpack2, max_capacity2) << endl;  // 133
    cout << glib::BackpackMaxValue(backpack3, max_capacity3) << endl;  // 388
    cout << glib::BackpackMaxValue2(backpack4, max_capacity4) << endl; // 334

    // 测试双 11 问题
    cout << "测试双 11 问题" << endl;
    vector<int> goods{11, 22, 15, 33, 9, 20, 48, 30, 66, 88};
    cout << glib::DoubleOneOne(goods, 200) << endl; // 200

    // 测试网格最短权重问题
    cout << "测试网格最短权重为" << endl;
    std::vector<std::vector<int>> grid = std::vector<std::vector<int>>(4, std::vector<int>(4, 0));
    grid[0][0] = 1;
    grid[0][1] = 3;
    grid[0][2] = 5;
    grid[0][3] = 9;
    grid[1][0] = 2;
    grid[1][1] = 1;
    grid[1][2] = 3;
    grid[1][3] = 4;
    grid[2][0] = 5;
    grid[2][1] = 2;
    grid[2][2] = 6;
    grid[2][3] = 7;
    grid[3][0] = 6;
    grid[3][1] = 8;
    grid[3][2] = 4;
    grid[3][3] = 3;
    std::deque<std::pair<int, int>> pos;
    pos.push_back(std::make_pair(0, 0));
    glib::MinPathBT(grid, 0, 0, grid[0][0], pos);
    for (auto ele : glib::Path)
        cout << ele.first << "," << ele.second << endl;
    cout << "状态转移表法" << endl;
    glib::StateTable(grid);
    cout << endl << "状态转移方程法" << endl;
    vector<vector<int>> mem = std::vector<std::vector<int>>(4, std::vector<int>(4, 0));
    cout << glib::StateTransitionEquation(grid, mem, 3, 3) << endl;

    return 0;
}
